package 括号匹配问题;

import java.util.Stack;

/*
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
 */
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        //toCharArray();方法作用是将字符串转为字符数组
        //因为本题中提到字符串中只有括号为单字符不用考虑存在字符数组中被拆分的问题所以可以这么使用
        char[] c = s.toCharArray();
        for (int i = 0; i < c.length; i++) {
            //判断是否为左括号,是左括号就入栈
            if (c[i] == '(' || c[i] == '[' || c[i] == '{'){
                stack.push(c[i]);
            }else {
                //如果队列为空就说明缺少左括号
                if(stack.empty()){
                    return false;
                }
                //定义字符ch作为临时变量存放栈顶元素
                char ch = stack.peek();
                //进行不同种类括号匹配的判断,成功就将栈顶元素弹出,否则就是括号种类不匹配
                if ((ch == '(' && c[i] == ')') ||
                        (ch == '[' && c[i] == ']') || (ch == '{' && c[i] == '}')){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }
        //直接返回stack.empty()的值,为空就说明字符串有效,不为空说明少右括号
        return stack.empty();
    }
}
